#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <stdbool.h>
#include <time.h>
#include "croututils.h"

void select_sort_int(int *base, int count)
{
    int swap;
    int imin, imax;
    int istart = 0;
    int istop = count - 1;

    while (istart < istop) {
	imin = istart;
	imax = istart;
	for (int i = istart; i <= istop; i++) {
	    if (base[i] < base[imin]) {
		imin = i;
	    }
	    if (base[i] > base[imax]) {
		imax = i;
	    }
	}

	swap = base[istart];
	base[istart] = base[imin];
	base[imin] = swap;
	if (imax == istart) {
	    imax = imin;
	}
	swap = base[istop];
	base[istop] = base[imax];
	base[imax] = swap;

	istart++;
	istop--;
    }
}


bool select_sort(void *base, size_t nobj, size_t size, comparator cmp)
{
    if (base == NULL || cmp == NULL || nobj <= 1 || size < 1) {
	return false;
    }

    char *swap = NULL;
    swap = (char *)malloc(size);
    if (swap == NULL) {
	return false;
    }

    int imin, imax, iter;

    int istart = 0;
    int istop = nobj - 1;
    while (istart < istop) {
	imin = istart;
	imax = istop;

	/* find the maximum and minimum positions */
	for (iter = istart+1; iter <= istop; iter++) {
	    if (cmp((char *)base+iter*size, (char *)base+imin*size) < 0) {
		imin = iter;
	    }
	    if (cmp((char *)base+iter*size, (char *)base+imax*size) > 0) {
		imax = iter;
	    }
	}

	/* swap 'imin' with 'istart' */
	if (istart != imin) {
	    memcpy(swap, (char *)base+istart*size, size);
	    memcpy((char *)base+istart*size, (char *)base+imin*size, size);
	    memcpy((char *)base+imin*size, swap, size);
	}

	/* check for repetition of 'imax' and 'istart' */
	if (imax == istart) {
	    /* the original value of 'istart' has already
	     * been moved to 'imin' position */
	    imax = imin;
	}

	/* swap 'imax' with 'stop' */
	if (istop != imax) {
	    memcpy(swap, (char *)base+istop*size, size);
	    memcpy((char *)base+istop*size, (char *)base+imax*size, size);
	    memcpy((char *)base+imax*size, swap, size);
	}

	istart++;
	istop--;
    }

    free(swap);
    return true;
}


#define ARRAY_COUNT 16

int main(int argc, char **argv)
{
    /*
    int array[ARRAY_COUNT] = {99, 13, 29, 78, 38, 78, 88, 11, 31, 9, 14, 27, 3, 8, 22, 69};
    */
    double array[ARRAY_COUNT];
    randarr_double(array, ARRAY_COUNT);

    listarr_double(array, ARRAY_COUNT);
    select_sort(array, ARRAY_COUNT, sizeof(array[0]), compare_double);
    listarr_double(array, ARRAY_COUNT);

    return 0;
}
